<?php
/**
 * The question_formulas_variables class to parse and evaluate variable string.
 *
 * @copyright &copy; 2010 Hon Wai, Lau
 * @author Hon Wai, Lau <lau65536@gmail.com>
 * @license http://www.gnu.org/copyleft/gpl.html GNU Public License version 3
 */


/**
 * Class contains method to parse variables text and evaluate variables.
 * 
 * It stores a set of name/values pair by parsing a string of assignments. 
 * These can be added to the class by either calling the constructor or using evaluate_additional_variables().
 * All variables evaluated a prior will be used in evaluate_numerical_expression() and substitute variables later.
 * 
 * Note that variables is a string of alpha-numeric character and '_' (not at the beginning). For example, 'A', 'is_added'
 */
class question_formulas_variables {
    private $all = array();  // store all variables that have been evaluated, always contains global variables
    private $parsed_random_vars_info = array(); // store the parsed information of random variables, for later instantiation
    
    
    /// return variables stored in this class
    function __construct($arr = array()) {
        if (is_array($arr))
            $this->all = $arr;
        else
            throw new Exception('Call to constructor with wrong parameter.');
    }
    
    
    /// return the array of all variables stored in this class, in the form of (variable name => values)
    function get_variables() {
        return $this->all;
    }
    
    
    /// return the variables of the input name stored in this class, null if not found
    function get_variable($name) {
        if (array_key_exists($name, $this->all))
            return $this->all[$name];
        else
            null;
    }
    
    
    /// @return a serialized string of variables in this class. It can be reconstructed by calling evaluate_additional_variables().
    function get_serialization() {
        $varsstr = array();
        foreach ($this->all as $name => $data) {
            $values = is_array($data) ? $data : array($data);   // convert all into array for homogeneous treatment
            foreach ($values as &$value)  if (is_string($value))
                $value = '"'.$value.'"';    // string has a quotation (note: there should be no quotation in the $value before)
            $varsstr[] = $name . '=' . (is_array($data) ? ('['.implode(',',$values).']') : $values[0]);
        }
        $result = implode(';', $varsstr);
        return strlen(trim($result)) == 0 ? '' : $result.';';
    }
    
    
    /**
     * Parse the random variables $assignments for later instantiation of a dataset. Throw on parsing error
     *
     * @param string $texts The variable assignment are string in the form of 'variable = expression' separated by ';'
     *   There are three type of expressions: (1) set of number or string (2) set of tuple (3) shuffle
     *   (1) When instantiating, one element will be drawn from the set, it also allow a range format of numbers
     *   (2) When instantiating, a tuple, say [0,0,0], will be drawn randomly from the set
     *   (3) When instantiating, a random shuffled tuple of the numbers will be created
     *   e.g. $input = "A={1,2,3}; B={1, 3:5, 8:9:.1}; C={"A","B"}; D={[1,4],[1,9]}; E={[1,"one"],[2,"two"]}; F=shuffle([0:10]);" ;
     */
    function parse_random_variables($texts) {
        $vars = array();
        $assignments = $this->check_and_split_assignments($texts, $vars, $tmpnames);
        
        /// identify different types and parse correspondingly.
        $parsedvars = array();
        foreach ($assignments as $assignment) {
            list($name, $expression) = $assignment;
            $var = new stdClass;
            
            // replace all [ ] brackets by a evaluated variable before moving on
            $stack = array();
            while (preg_match('/\[[^\[\]]*\]/', $expression, $matches)) {  // foreach matched [ ] bracket
                $tmpname = $this->replace_by_variable(&$expression, $matches[0], &$vars, null, &$tmpnames);
                $stack[] = array($tmpname, $matches[0]);    // replace the [ ] by a temporary variable, and push the content in the stack
            }
            try {
                $this->evaluate_assignments_stack_recursively(array_reverse($stack), $vars, $tmpnames);
            } catch (Exception $e) {
                throw new Exception($name.': '.get_string('error_randvars_type','qtype_formulas'));
            }
                
            if ( $expression[0] == '{' && $expression[strlen($expression)-1] == '}') {
                // get each individual elements in the set
                $elements = explode(',', substr($expression,1,-1));
                foreach ($elements as $z => $element)  $elements[$z] = trim($element);
                $first = $elements[0];
                
                // get the type of the first element
                if (count(explode(':', $first)) > 1)
                    $type = 'double';
                else if (array_key_exists($first, $vars))
                    $type = gettype($vars[$first]);
                else if ($first[0] == '-' && array_key_exists(trim(substr($first,1)), $vars))
                    $type = 'double';
                else
                    throw new Exception($name.': '.get_string('error_randvars_type','qtype_formulas'));
                
                // preform the corresponding parsing for each type
                if ($type == 'integer' || $type == 'double') {  // for set of number
                    $var->type = 'set_number';
                    $var->elementssize = 0;
                    foreach ($elements as $element) {
                        $tmpex = explode(':', $element);
                        if (count($tmpex) > 3)
                            throw new Exception($name.': '.get_string('error_randvars_range','qtype_formulas'));
                        $ex = array();
                        $signs = array_fill(0, count($tmpex), +1);
                        foreach ($tmpex as $w => $e) {
                            $e = trim($e);
                            if (strlen($e) > 0)  if ($e[0] == '-') {    // the deficiency of number substitution
                                $signs[$w] = -1;  // it only get the positive number, so a negative sign is left here
                                $e = trim(substr($e, 1));
                            }
                            $ex[$w] = $e;
                        }
                        foreach ($ex as $e)  if (!array_key_exists($e,$vars))
                            throw new Exception($name.': '.get_string('error_randvars_general','qtype_formulas'));
                        else if (gettype($vars[$e]) != 'integer' && gettype($vars[$e]) != 'double')
                            throw new Exception($name.': '.get_string('error_randvars_type','qtype_formulas'));
                        $startpoint = $vars[$ex[0]]*$signs[0];
                        $endpoint = count($ex) >= 2 ? $vars[$ex[1]]*$signs[1] : $startpoint + 0.5;
                        $interval = count($ex) == 3 ? $vars[$ex[2]]*$signs[2] : 1.;
                        $var->numelement += ceil( ($endpoint-$startpoint)/$interval );
                        $var->elements[] = array($startpoint, $endpoint, $interval);
                    }
                }
                else if ($type == 'string' || $type == 'array') {   // for set of element (string or array)
                    $var->type = 'set_element';
                    $var->numelement = count($elements);
                    foreach ($elements as $element) {   // check whether each elements is a defined variable
                        if (!array_key_exists($element, $vars))
                            throw new Exception($name.': '.get_string('error_randvars_general','qtype_formulas'));
                        $var->elements[] = $vars[$element];
                    }
                    if ($type == 'string')  foreach ($var->elements as $element) {  // type check, all element must also a string
                        if (gettype($element) != 'string')
                            throw new Exception($name.': '.get_string('error_randvars_type','qtype_formulas'));
                    }
                    if ($type == 'array')  foreach ($var->elements as $element) {   // elements at the same location must also a string
                        foreach ($element as $z => $e)  if (gettype($e) != gettype($var->elements[0][$z]))
                            throw new Exception($name.': '.get_string('error_randvars_type','qtype_formulas'));
                    }
                }
            }
            else if ( preg_match('/^shuffle\s*\(\s*([\w@]+)\s*\)$/', $expression, $matches) ) {
                $var->type = 'shuffle';
                if (!array_key_exists($matches[1], $vars))
                    throw new Exception($name.': '.get_string('error_randvars_general','qtype_formulas'));
                $var->numelement = count($vars[$matches[1]]);   // the actual number should be a!, but it is not used
                $var->elements = $vars[$matches[1]];
                foreach ($var->elements as $e)  if (gettype($e) != gettype($var->elements[0]))
                    throw new Exception($name.': '.get_string('error_randvars_type','qtype_formulas'));
            }
            else throw new Exception($name.': '.get_string('error_randvars_general','qtype_formulas'));
            
            // There must be at least two elements to draw from, otherwise it is not a random variable
            if ($var->numelement < 2)
                throw new Exception($name.': '.get_string('error_randvars_set_size','qtype_formulas'));
            $var->expression = $expression;
            $parsedvars[$name] = $var;
        }
        $this->parsed_random_vars_info = $parsedvars;
    }
    
    
    /**
     * Instantiate a particular set of random variables and store in this class. All previous variables are erased. No throw
     */
    function instantiate_random_variables() {
        foreach ($this->parsed_random_vars_info as $name => $var) {
            if ( $var->type == 'set_number' ) {
                $id = mt_rand(0,$var->numelement-1);
                foreach ($var->elements as $elem) {
                    $sz = ceil( ($elem[1]-$elem[0])/$elem[2] );
                    if ( $id < $sz) {
                        $this->add_variable( $name , $elem[0] + $id*$elem[2]);
                        break;
                    }
                    $id -= $sz;
                }
            }
            else if ( $var->type == 'set_element' ) {
                $id = mt_rand(0,$var->numelement-1);
                $this->add_variable( $name , $var->elements[$id] );
            }
            else if ( $var->type == 'shuffle') {
                $tmp = $var->elements;
                shuffle($tmp);
                $this->add_variable( $name , $tmp );
            }
        }
    }
    
    
    /**
     * Evaluate local variables assignments and add them to this class. May throw error
     * 
     * @param string $texts The string containing the definition of variables assignments.
     */
    function evaluate_additional_variables($texts) {
        $assignments = $this->check_and_split_assignments($texts, $this->all, $tmpnames);
        foreach ($assignments as $i => $assignment)  try {
            $this->evaluate_assignments_stack_recursively(array($assignment), $this->all, $tmpnames);
        } catch (Exception $e) {
            throw new Exception(($i+1).': '.$assignment[0].': '.$e->getMessage());
        }
        $this->remove_all_temporary_name_in_variables($tmpnames, $this->all);
    }
    
    
    /**
     * Evaluate the $expression with all variables given in the $vars. May throw error
     * 
     * @param string $expression The expression being evaluated
     * @param array $vars The variable list for substitution. Internal variable will be used if it is not given.
     * @return The evaluated result, a floating point number.
     */
    function evaluate_numerical_expression($expression, &$vars = null) {
        // use internal variable list if it is not given in the parameter
        if (!isset($vars))  $vars = &$this->all;
        
        // replace the variables by value. The $expression here should contain only variables of number. Other type are error
        $subs = $this->substitute_variables_in_formula($expression, $vars);
        
        // check for possible formula error for the substituted string, before directly calling eval()
        $res = $this->find_formula_errors($subs);
        if ($res)  throw new Exception('For expression: ' . $expression . "\n" . $res);
        
        // after checking, it should contains pure code of mathematical expression, evaluate the expression by eval()
        unset($evaluated);
        eval('$evaluated = '.$subs.';');
        if (!isset($evaluated))  throw new Exception(get_string('error_evaluation_general','qtype_formulas') . $expression);
        return floatval($evaluated);
    }
    
    
    /**
     * Add one variable to the variable lists in this class. No error check, no throw
     * 
     * @param string $name the name of the variable
     * @param mixed $data the data of the variable, it should be a number, a string or an array of number or string
     * @param array $vars the variable list that the $data will be assign to. If not given, use the one in this class
     */
    function add_variable($name, $data, &$vars = null) {
        // use internal variable list if it is not given in the parameter
        if (!isset($vars))  $vars = &$this->all;
        
        // simple test of array-index format element, it should only be used internally
        if (strpos($name, '[') === false) { 
            $vars[$name] = $data;  // directly assign the $data to the name
            return;
        }
        
        // Here the name should be an variable with array index, check it before assign it
        $variable_format = '([A-Za-z_@][A-Za-z0-9_]*)\[([0-9]+)\]';
        if (!preg_match('/^'.$variable_format.'$/', $name, $matches))
            throw new Exception(get_string('error_vars_format','qtype_formulas'));
        $name = $matches[1];
        $index = $matches[2];
        if (is_array($data))    // the $data cannot be an array
            throw new Exception(get_string('error_vars_array_no_nested','qtype_formulas'));
        if (!array_key_exists($name, $vars) || !array_key_exists($index, $vars[$name]))
            throw new Exception(get_string('error_vars_array_not_defined','qtype_formulas'));
        if (gettype($vars[$name][$index]) != gettype($data))    // type of entry must be the same as before, to guarantee all elements are of same type
            throw new Exception(get_string('error_vars_array_type','qtype_formulas'));
        $vars[$name][$index] = $data;
    }
    
    
    /**
     * Replace the variables in the input $str by all variables in this class. No throw
     * 
     * @param string $str The string being replaced, with variables in the format of, say, {A}, {B}[0]
     * @return The replaced string
     */
    function substitute_variables_in_text($text) {
        $variable_format = '\{([A-Za-z][A-Za-z0-9_]*)(\[([0-9]+)\])?\}';    // find all possible variables
        if (!preg_match_all('/'.$variable_format.'/', $text, $matches))  return $text;  // if no match, do nothing
        foreach ($matches[1] as $i => $name) {  // replace all known variables, and skip other
            if (!array_key_exists($name, $this->all))  continue;
            $value = $this->all[$name];
            if (is_array($value)) {
                if (!array_key_exists($matches[3][$i], $value))  continue;
                $value = $value[$matches[3][$i]];
            }
            $text = str_replace($matches[0][$i], $value, $text);
        }
        return $text;
    }
    
    
    
    
    
    /**
     * Replace the variables in the input $str by all variables in this class. No throw
     * 
     * @param string $str The formula being replaced
     * @param array $vars The variables list, used to substitute the variables in the $formula
     * @return The replaced string
     */
    function substitute_variables_in_formula($formula, $vars) {
        $variable_format = '([^A-Za-z0-9_@]*)([A-Za-z_@][A-Za-z0-9_]*)([^A-Za-z0-9_@]*)';    // only simple named variables
        $partitions = explode("\n", preg_replace('/'.$variable_format.'/', '${1}'."\n".'${2}'."\n".'${3}', $formula));
        if (count($partitions) == 1)  return $formula;  // no any variable candidate
        foreach ($partitions as $i => &$name)  if ($i % 2 == 1)  { // odd number is the match candidate variable
            if (!array_key_exists($name, $vars))  continue;    // if the candidate string is not in the variables list, skip
            $value = $vars[$name];
            if (!is_numeric($value))    // only numeric variable can be referred in a formula
                throw new Exception(get_string('error_evaluation_nonnumeric','qtype_formulas'));
            $name = $value;
        }
        return implode(' ', $partitions);    // note the partitions always have odd number of elements
    }
    
    
    /**
     * Ensure the $assignments is in the form of 'name = expression;' and put them in a stack. Throw on parsing error
     * 
     * @param string $texts the text of variables definition. The string and range will be substituted after calling.
     * @param string $vars Temporary variables will be added here.
     * @param string $tmpnames The names of temporary variables, for later removal.
     * @return a stack. Represented by an array in the form (name => expression)
     */
    function check_and_split_assignments(&$texts, &$vars, &$tmpnames) {
        $this->replace_string_by_variables(&$texts, &$vars, &$tmpnames);
        
        /// split the $varsdeftext into different $assignments, separated by ';'
        $assignments = explode(';', $texts);
        if (strlen(trim(array_pop($assignments))) != 0)
            throw new Exception(get_string('error_vars_end_separator','qtype_formulas'));
        
        /// split the $assignment into the pairs form of name = expression;
        $variable_format = '[A-Za-z][A-Za-z0-9_]*(\[[0-9]+\])?';
        $allowableoperatorchar = '-+/*%>:^\~<?=&|!,)(}{\]\[' . '@';
        $stack = array();
        foreach ($assignments as $i => $assignment) {
            $ex = explode('=', $assignment, 2);
            if (count($ex) != 2)
                throw new Exception(($i+1).': '.get_string('error_vars_parse','qtype_formulas'));
            $name = trim($ex[0]);
            $expression = trim($ex[1]);
            if (!preg_match('/^'.$variable_format.'$/', $name))
                throw new Exception(get_string('error_vars_format','qtype_formulas') . $name);
            if (strlen($expression) == 0)   // the right hand side should be of non-zero length
                throw new Exception(($i+1).': '.$name.': '.get_string('error_vars_parse','qtype_formulas'));
            $this->replace_fixed_range_by_variables(&$expression, &$vars, &$tmpnames);
            $this->replace_number_by_variables(&$expression, &$vars, &$tmpnames);
            if (!preg_match('~^[\w\s'.$allowableoperatorchar.']*$~', $expression))   // the result expression should contains simple characters only
                throw new Exception(($i+1).': '.$name.': '.get_string('error_vars_forbid_char','qtype_formulas'));
            $stack[] = array($name, $expression);
        }
        return $stack;
    }
    
    
    /// replace the strings in the $texts by variables with new names in $tmpnames, and add it to the $vars
    function replace_string_by_variables(&$texts, &$vars, &$tmpnames) {
        $texts = stripcslashes($texts);
        $ex = explode("\"", $texts);
        if (count($ex) == 1)  return;  // no string in the assignments, so leave
        if (count($ex) % 2 == 0)  throw new Exception(get_string('error_vars_string','qtype_formulas'));
        foreach ($ex as $i => &$s)  if ($i % 2 == 1)  {
            if (strpos($s, '\'') !== false || strpos($s, "\n") !== false)
                throw new Exception(get_string('error_vars_string','qtype_formulas'));
            $s = $this->replace_by_variable(&$notuse, null, &$vars, $s, &$tmpnames);
        }
        else if (strpos($s, '@') !== false) // @ is reserved for temp var, so it cannot be used in the main text
            throw new Exception(get_string('error_vars_forbid_char','qtype_formulas'));
        $texts = implode(' ', $ex);
    }
    
    
    /// replace the fixed range of the form [a:b] in the $texts by variables with new names in $tmpnames, and add it to the $vars
    function replace_fixed_range_by_variables(&$texts, &$vars, &$tmpnames) {
        $fixed_range_pattern = '\[([0-9]+):([0-9]+)(:([0-9]+))?\]';
        if (!preg_match_all('/'.$fixed_range_pattern.'/', $texts, $matches))  return;
        foreach ($matches[0] as $i => $placeholder) {
            $data = array();
            $step = strlen($matches[4][$i]) != 0 ? floatval($matches[4][$i]) : 1.;
            for ($z=floatval($matches[1][$i]); $z<floatval($matches[2][$i]); $z += $step) {
                $data[] = $z;
                if (count($data) > 100)  throw new Exception(get_string('error_vars_array_size','qtype_formulas'));
            }
            if (count($data) < 2)  throw new Exception(get_string('error_vars_array_size','qtype_formulas'));
            $this->replace_by_variable(&$texts, $placeholder, &$vars, $data, &$tmpnames);
        }
    }
    
    
    /// replace all number by variables, and perform some checks
    function replace_number_by_variables(&$texts, &$vars, &$tmpnames) {
        // The following pattern does not capture all false terms, such as a1.1 or 2.2b, but those will evaluate to false during eval()
        $number_term_pattern = '[\w.]*[0-9]*\.?[0-9]+([eE][-+]?[0-9]+)?[\w.]*'; // . is not allowable operator, so check it here
        if (!preg_match_all('/'.$number_term_pattern.'/', $texts, $matches))  return;
        $others = preg_split('/'.$number_term_pattern.'/', $texts);
        $texts = '';
        foreach ($matches[0] as $i => $m) {
            $pre = $others[$i];
            if (is_numeric($m)) {   // If $m is a number without other word (\w.) surrounding it
                if (empty($pre) || $pre[strlen($pre)-1] != '@') {   // If it is a number and not prefixing with '@' (temp variable)
                    $tmpname = $this->replace_by_variable(&$notuse, null, &$vars, floatval($m), &$tmpnames);
                    $texts .= $others[$i] . ' ' . $tmpname .' ';    // Note: $m only get the positive part of the number
                }
                else
                    $texts .= $others[$i] . $m; // if it has '@' prefixing it, add this segment back
                continue;
            }
            // it should only occurs during validation phase, otherwise it should syntax error
            $variable_format = '[A-Za-z_][A-Za-z0-9_]*';
            if (!preg_match('/^'.$variable_format.'$/', $m, $tt)) // false alarm will raise for the form aa1e-1, which should be rare though
                throw new Exception(get_string('error_vars_parse','qtype_formulas'));
            $texts .= $others[$i] . $m; // if it is of the variable form, concatenate back to the $text
        }
        $texts .= end($others);
    }
    
    
    /**
     * Evaluate the assignments in the stack recursively until there is nothing left. Throw on error
     * 
     * @param string $stack the stack of assignments, in the form of (order reversed) array of array(name, expression)
     * @param array $vars The variable array contains value that will substitute variable in assignments in $stack
     * @param mixed $data the data of the variable, it should be a number or array of number (for tuple)
     */
    function evaluate_assignments_stack_recursively($stack, &$vars, &$tmpnames) {
        $loop_count = 0;
        while (count($stack) > 0) {
            //if ($loop_count++ > 1000)  throw new Exception('Evaluation takes more than 1000 ops for each expression, probably a bugs.');
            //var_dump($stack);//,$vars, $tmpnames);//flush();
            $match = $this->handle_simple_assignment(&$stack, &$vars, &$tmpnames);
            if ($match)  continue;
            $match = $this->handle_for_in_syntax(&$stack, &$vars, &$tmpnames);
            if ($match)  continue;
            $match = $this->handle_square_bracket_syntax(&$stack, &$vars, &$tmpnames);
            if ($match)  continue;
            $match = $this->handle_special_functions(&$stack, &$vars, &$tmpnames);
            if ($match)  continue;
            $expression = &$stack[count($stack)-1][1];
            $res = $this->evaluate_numerical_expression($expression, $vars);
            // The value in $res is assigned in the next round in the handle simple assignment()
            $expression = $this->replace_by_variable(&$notuse, null, &$vars, $res, &$tmpnames);
        }
    }
    
    
    /// If the top of the stack is a number or a variable, pop it and assign it to the variable name
    /// @return boolean of whether this syntax is found
    function handle_simple_assignment(&$stack, &$vars, &$tmpnames) {
        list($name, $expression) = end($stack);
        
        // get the value on the right hand side
        $expression = trim($expression);
        if (strlen($expression) == 0)     // Check whether expression is empty
            throw new Exception(get_string('error_subexpression_empty','qtype_formulas'));
        
        if (array_key_exists($expression, $vars))   // if the variable name already exist, directly assign it
            $value = $vars[$expression];
        else if ($expression[0] = '+' || $expression[0] = '-') {
            $sign = $expression[0];
            $tmp = trim(substr($expression,1));
            if (array_key_exists($tmp, $vars))
                $value = $sign == '+' ? $vars[$tmp] : -$vars[$tmp];
            else
                return false;
        }
        else
            return false;
        
        // Assign value to the $name. Then remove the top element in the stack as this assignment is done.
        $this->add_variable($name, $value, $vars);
        array_pop($stack);  
        return true;
    }
    
    
    /// replace the [A[i]*B[i] for i in [0:3]] by a set of unrolled assignments in the $stack for later evaluation.
    /// @return boolean of whether this syntax is found or not
    function handle_for_in_syntax(&$stack, &$vars, &$tmpnames) {
        return false;
    }
    
    
    /// handle the array by replacing it by variable, if necessary, evaluate subexpression by putting it in the $stack.
    /// @return boolean of whether this syntax is found or not
    function handle_square_bracket_syntax(&$stack, &$vars, &$tmpnames) {
        $expression = &$stack[count($stack)-1][1];  // the expression will be modified
        // find whether there is any bracket in the expression, optionally find the variable preceding it
        if (!preg_match('/([\w@]+)?\s*\[([^\[\]]*)\]/', $expression, $matches))  return false;
        // The inner bracket [] will be replaced first
        $v = $matches[1];   // content stores the string inside the []
        $content = trim($matches[2]);   // content stores the string inside the []
        if (strlen($v) == 0) {  // case: if it has no string preceding it, then it should be an array
            $ex = explode(',', $content);   // split the content in [] by comma
            if (count($ex) < 2 || count($ex) > 100)
                throw new Exception(get_string('error_vars_array_size','qtype_formulas'));
            // the type of the first element must be known. Otherwise, evaluate the first element before moving on the later part
            if (!array_key_exists(trim($ex[0]), $vars)) {
                $tn = $this->next_temporary_name($tmpnames);
                array_push($stack, array($tn, $ex[0]));    // evaluate the first element of the array
                $ex[0] = $tn;   // put the temporary name at the first location
                $expression = str_replace($matches[0], '['.implode(',',$ex).']', $expression);  // merge the string back
                return true;    // come back later
            }
            // the array key should exists after the part above, check the type first and then copy its 'type' to all other variables.
            $tmparray = array_fill(0, count($ex), $vars[trim($ex[0])]);   // copy the 'type' of the first element, nested array will be checked later
            // replace the [ ] by a temporary variable. $ex is used, but it's value will be overrided by evaluated result later.
            $tmpname = $this->replace_by_variable(&$expression, $matches[0], &$vars, $tmparray, &$tmpnames);
            // push the subexpression in the stack so the evaluated element will be assigned to the corresponding array entry later
            foreach ($ex as $z => &$e)  array_push($stack, array($tmpname.'['.$z.']', $e));
            return true;
        }
        else {
            if (!array_key_exists($content, $vars)) {   // probably the $content contains expressions that need to evaluate
                $tn = $this->next_temporary_name($tmpnames);
                $expression = str_replace($matches[0], $matches[1].'['.$tn.']', $expression);
                array_push($stack, array($tn, $content));    // the content will be evaluated first
                return true;
            }
            if (!array_key_exists($v,$vars) || !is_array($vars[$v]))
                throw new Exception(get_string('error_vars_not_defined','qtype_formulas'));
            $arr = $vars[$v];
            $index = $vars[$content];
            if (!is_numeric($index))    // array key must be numeric
                throw new Exception(get_string('error_vars_array_index_nonnumeric','qtype_formulas'));
            if ($index < 0 || $index >= count($arr))    // index out of range cannot be checked during validation!!!!!!
                throw new Exception(get_string('error_vars_array_index_out_of_range','qtype_formulas'));
            $this->replace_by_variable(&$expression, $matches[0], &$vars, $arr[$index], &$tmpnames);
        }
        return true;
    }
    
    
    /// handle the few function for the array of number or string
    /// @return boolean of whether this syntax is found or not
    function handle_special_functions(&$stack, &$vars, &$tmpnames) {
        $expression = &$stack[count($stack)-1][1];
        $function_name = array('join','map','sum','sort');
        $pattern = '('.implode('|',$function_name).')\s*\(([\w\s,@]+)\)';
        if (!preg_match('/'.$pattern.'/', $expression, $matches))  return false;
        
        // if match any one of the above function, get the parameter list of the function
        $ex = explode(',', $matches[2]);
        $params = array();
        foreach ($ex as $i => $e) {
            $e = trim($e);
            if (!array_key_exists($e, $vars))
                throw new Exception(get_string('error_vars_not_defined','qtype_formulas'));
            $params[] = $vars[$e];
        }
        
        // perform the operation for each of these functions
        if ($matches[1] == 'join') {   // take two parameters: separator and array
            return false;   // temporary remove this function, need to check later ... ...
            if (!$this->signature_match($params, array('string','array'), false))
                throw new Exception(get_string('error_func_param','qtype_formulas') . $matches[0]);
            
            $res = join($params[0], $params[1]);
        }
        else if ($matches[1] == 'map') {    // take two/three parameters: unary/binary operator and one/two numeric array
            if (!$this->signature_match($params, array('string','array')) &&
                !$this->signature_match($params, array('string','array','array')) &&
                !$this->signature_match($params, array('string','double','array')) &&
                !$this->signature_match($params, array('string','array','double')) )
                throw new Exception(get_string('error_func_param','qtype_formulas') . $matches[0]);
            if (count($params) == 2) {  // two parameters, unary operator
                $unary_functions = array_flip( array('abs', 'acos', 'acosh', 'asin', 'asinh', 'atan', 'atanh', 'ceil'
                    , 'cos', 'cosh' , 'deg2rad', 'exp', 'expm1', 'floor', 'is_finite', 'is_infinite', 'is_nan'
                    , 'log10', 'log1p', 'rad2deg', 'sin', 'sinh', 'sqrt', 'tan', 'tanh', 'log', 'round') );
                if (!array_key_exists($params[0], $unary_functions))
                    throw new Exception(get_string('error_func_param','qtype_formulas') . $matches[0]);
                
                $res = array_map(create_function('$a', 'return '.$params[0].'($a);'), $params[1]);
            }
            else {  // three parameters, binary operator
                $binary_functions = array_flip( array('log', 'round', 'atan2', 'fmod', 'pow', 'min', 'max') );
                $binary_operators = array_flip( array('+','-','*','/','%','>','<','==','&&','||','&','|','<<','>>','^') );
                if (!is_array($params[1]))  $params[1] = array_fill(0, count($params[2]), $params[1]);
                if (!is_array($params[2]))  $params[2] = array_fill(0, count($params[1]), $params[2]);
                if (count($params[1]) != count($params[1]))
                    throw new Exception(get_string('error_func_param','qtype_formulas') . $matches[0]);
                
                if (array_key_exists($params[0], $binary_operators))
                    $res = array_map(create_function('$a,$b', 'return ($a)'.$params[0].'($b);'), $params[1], $params[2]);
                else if (array_key_exists($params[0], $binary_functions))
                    $res = array_map(create_function('$a,$b', 'return '.$params[0].'($a,$b);'), $params[1], $params[2]);
                else
                    throw new Exception(get_string('error_func_param','qtype_formulas') . $matches[0]);
            }
            array_walk($res, create_function('&$v', '$v = floatval($v);'));
        }
        else if ($matches[1] == 'sum') {    // take two parameters: binary operator and numeric array
            if (!$this->signature_match($params, array('array')) &&
                !$this->signature_match($params, array('array','string')) )
                throw new Exception(get_string('error_func_param','qtype_formulas') . $matches[0]);
            if (!isset($params[1]))  $params[1] = '+';
            $binary_operators = array_flip( array('+','||','&&','==','*') );
            if (!array_key_exists($params[1], $binary_operators))
                throw new Exception(get_string('error_func_param','qtype_formulas') . $matches[0]);
            
            $res = array_shift($params[0]); // array must have at least one element in this class
            $res = array_reduce($params[0], create_function('$a,$b','return ($a)'.$params[1].'($b);'), $res);
            $res = floatval($res);
        }
        else if ($matches[1] == 'sort') {   // take one parameter: numeric array
            return false;   // temporary remove this function, need to check later ... ...
            if (!$this->signature_match($params, array('array')))
                throw new Exception(get_string('error_func_param','qtype_formulas') . $matches[0]);
            
            $res = $params[0];
            sort($res);
        }
        else
            return false;
        $this->replace_by_variable(&$expression, $matches[0], &$vars, $res, &$tmpnames);
        return true;
    }
    
    
    /// check whether the type of parameters of special function. Also check whether the array is numeric
    function signature_match($parameters, $expected, $numeric_check = true) {
        if (count($parameters) != count($expected))
            return false;       // check size
        foreach ($parameters as $i => $parameter)  if (gettype($parameter) != $expected[$i])
            return false;       // check type
        foreach ($parameters as $i => $parameter)  if ($numeric_check && gettype($parameter) == 'array') {
            foreach ($parameter as $elem)  if (!is_numeric($elem))
                return false;   // check numeric array
        }
        return true;
    }
    
    
    /// replace the $sub in the $expression by a name of temporary variable, and add the $value to the $vars
    /// if $sub is null, $tmpname will be assigned to $expression
    /// if $value is null, no varaible will be added to the $vars
    /// $return the temporary name of the variable
    function replace_by_variable(&$expression, $sub, &$vars, $value, &$tmpnames) {
        $tmpname = $this->next_temporary_name($tmpnames);    // get a temporary variable name
        if (isset($value))     // if there is input value for the temporary variable
            $vars[$tmpname] = $value;     // add the variable values to the variable list
        if (isset($sub))       // if there is no substituting text, directly assign the temp name to the expression
            $expression = str_replace($sub, ' '.$tmpname.' ', $expression);  // replace the pattern by the name
        return $tmpname; 
    }
    
    
    /// Return an available temporary name, which are used to evaluated subexpression in assignments.
    function next_temporary_name(&$tmpnames) {
        if (!isset($tmpnames))  $tmpnames = 0;  // All temporary variables are prefixed by @
        return '@'.($tmpnames++);   // Note that @ is not an allowable char used in variable definition.
    }
    
    
    /// Remove all temporary variables in $vars
    function remove_all_temporary_name_in_variables(&$tmpnames, &$vars) {
        $tmp = array(); // temporary array, only stores non-temporary variables
        foreach ($vars as $name => $data)  if ($name[0] != '@')  $tmp[$name] = $data;
        $vars = $tmp;
    }
    
    
    
    
    
    /**
     * Check the validity of formula. From calculated question type. Modified.
     * 
     * @param string $formula The input formula
     * @return false for possible valid formula, otherwise error message
     */
    function find_formula_errors($formula) {
    /// Validates the formula submitted from the question edit page.
    /// Returns false if everything is alright.
    /// Otherwise it constructs an error message
        // Strip away empty space and lowercase it
        $formula = str_replace(' ', '', $formula);

        $safeoperatorchar = '-+/*%>:^\~<?=&|!'; /* */
        $operatorornumber = "[$safeoperatorchar.0-9eE]";

        while ( preg_match("~(^|[$safeoperatorchar,(])([a-z0-9_]*)\\(($operatorornumber+(,$operatorornumber+((,$operatorornumber+)+)?)?)?\\)~",
            $formula, $regs)) {
            for ($i=0; $i<6; $i++)  if (!isset($regs[$i]))  $regs[] = '';
            switch ($regs[2]) {
                // Simple parenthesis
                case '':
                    if (strlen($regs[4])!=0 || strlen($regs[3])==0) {
                        return get_string('illegalformulasyntax', 'quiz', $regs[0]);
                    }
                    break;

                // Zero argument functions
                case 'pi':
                    if (strlen($regs[3])!=0) {
                        return get_string('functiontakesnoargs', 'quiz', $regs[2]);
                    }
                    break;

                // Single argument functions (the most common case)
                case 'abs': case 'acos': case 'acosh': case 'asin': case 'asinh':
                case 'atan': case 'atanh': case 'bindec': case 'ceil': case 'cos':
                case 'cosh': case 'decbin': case 'decoct': case 'deg2rad':
                case 'exp': case 'expm1': case 'floor': case 'is_finite':
                case 'is_infinite': case 'is_nan': case 'log10': case 'log1p':
                case 'octdec': case 'rad2deg': case 'sin': case 'sinh': case 'sqrt':
                case 'tan': case 'tanh':
                    if (strlen($regs[4])!=0 || strlen($regs[3])==0) {
                        return get_string('functiontakesonearg','quiz',$regs[2]);
                    }
                    break;

                // Functions that take one or two arguments
                case 'log': case 'round':
                    if (strlen($regs[5])!=0 || strlen($regs[3])==0) {
                        return get_string('functiontakesoneortwoargs','quiz',$regs[2]);
                    }
                    break;

                // Functions that must have two arguments
                case 'atan2': case 'fmod': case 'pow':
                    if (strlen($regs[5])!=0 || strlen($regs[4])==0) {
                        return get_string('functiontakestwoargs', 'quiz', $regs[2]);
                    }
                    break;

                // Functions that take two or more arguments
                case 'min': case 'max':
                    if (strlen($regs[4])==0) {
                        return get_string('functiontakesatleasttwo','quiz',$regs[2]);
                    }
                    break;

                default:
                    return get_string('unsupportedformulafunction','quiz',$regs[2]);
            }

            // Exchange the function call with '1' and then chack for
            // another function call...
            if ($regs[1]) {
                // The function call is proceeded by an operator
                $formula = str_replace($regs[0], $regs[1] . '1', $formula);
            } else {
                // The function call starts the formula
                $formula = preg_replace("~^$regs[2]\\([^)]*\\)~", '1', $formula);
            }
        }

        if (preg_match("~[^$safeoperatorchar.0-9eE]+~", $formula, $regs)) {
            return get_string('illegalformulasyntax', 'quiz', $regs[0]);
        } else {
            // Formula just might be valid
            return false;
        }

    }
    
}


?>
